import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-29
 * Time: 15:57
 */
public class Solution {
    /**
     * 283:移动零
     * 网址：https://leetcode.cn/problems/move-zeroes/
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        int[] array = new int[nums.length];
        int count = 0;//记录0的个数
        int index = 0;//array的下标
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) {
                array[index++] = nums[i];
            } else {
                count++;
            }
        }
        while(count != 0) {
            array[index++] = 0;
            count--;
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = array[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 3, 12};
        moveZeroes(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("============");
    }
    /**
     * LeetCode题：88合并两个有序数组
     * 地址：https://leetcode.cn/problems/merge-sorted-array/description/
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        //暴力求法 O(M * N)
        for(int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        //O(N)
        //定义一个新的数组，这个数组就是我们排完序的数组，把这个数组的元素赋值给数组nums1
        int[] newNum = new int[m + n];
        //遍历nums1和nums2数组，比较这两个数组，谁小先放进新的数组中
        int nums1Index = 0;
        int nums2Index = 0;
        for(int index = 0; index < m + n; index++) {
            if(nums1Index >= m) {
                //nums1遍历完了，把剩下的nums2全部依次放进newNum中
                newNum[index] = nums2[nums2Index++];
            } else if(nums2Index >= n) {
                //nums2遍历完了，把剩下的nums1全部依次放进newNum中
                newNum[index] = nums1[nums1Index++];
            } else if(nums1[nums1Index] < nums2[nums2Index]){
                //nums1和nums2都没遍历完，要进行比较,谁小把谁先放进newNum中
                newNum[index] = nums1[nums1Index++];
            }else{
                newNum[index] = nums2[nums2Index++];
            }
        }
        //把newNum数组元素全部放进nums1中
        for(int i = 0; i < n + m; i++) {
            nums1[i] = newNum[i];
        }
    }
    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        //O(N)
        //定义两个下标分别遍历nums1和nums2，从第m-1和第n-1开始往前走，谁大，把它放到nums1的最后一个下标，第二大就放在nums1倒数第二个下标，依次类推
        int nums1Index = m - 1;
        int nums2Index = n - 1;
        for(int index = m + n - 1; index >= 0; index--){
            if(nums1Index < 0) {
                nums1[index] = nums2[nums2Index--];
            } else if(nums2Index < 0) {
                break;
            } else if(nums1[nums1Index] > nums2[nums2Index]) {
                nums1[index] = nums1[nums1Index--];
            } else{
                nums1[index] = nums2[nums2Index--];
            }
        }
    }
}
